home *** CD-ROM | disk | FTP | other *** search
/ TPUG - Toronto PET Users Group / TPUG Users Group CD / TPUG Users Group CD.iso / AMIGA / AMICUS / AMIBEST4.ADF / AmigaBasicStuff / BasicSorts / InsertionSort < prev    next >
Text File  |  1987-07-22  |  657b  |  30 lines
  1. sub InsertionSort ( x$(), n% ) static
  2.  
  3.      '  Sort x(1..n) , n > 1
  4.      '  Invariant  :  x(1..i-1) is sorted
  5.      '
  6.      '  An O(n^2) algorithm...
  7.      '
  8.      '
  9.      FOR i = 2 TO n%
  10.           j=i
  11.           t$=x$(j)
  12.           Jail:
  13.                IF j <= 1 OR x$(j-1) <=t$ THEN HaveATogaParty
  14.                x$(j) = x$(j-1)
  15.                j = j - 1
  16.                GOTO Jail
  17.           HaveATogaParty:
  18.                x$(j) = t$
  19.      NEXT
  20.  
  21.      '
  22.      ' Algorithm from Programming Pearls by John Bentley
  23.      '     from AT&T Bell Laboratories.
  24.      '
  25.      ' Implemented in AmigaBasic by Gregory A. Kendall
  26.      '     from Brendallson Software.
  27.      '
  28.  
  29. end sub
  30.